home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / REGEXP.C < prev    next >
C/C++ Source or Header  |  1992-08-12  |  34KB  |  1,192 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MNF 06/13/89 -- Initial Design and Implementation
  14. // Updated: MBN 09/08/89 -- Added conditional exception handling
  15. // Updated: MBN 12/15/89 -- Sprinkled "const" qualifiers all over the place!
  16. // Updated: MJF 03/12/90 -- Added group names to RAISE
  17. // Updated: DLS 03/22/91 -- New lite version
  18. //
  19. // This file contains the implementation for the member functions of the CoolRegexp
  20. // class.  The  CoolRegexp class is  defined  in the  CoolRegexp.h   header file.  More
  21. // documentation is also available  in that file.   A  significant part of this
  22. // file is derived directly from other work done on regular expressions.   That
  23. // part is so marked.
  24. //
  25.  
  26. #ifndef REGEXPH                    // If CoolRegexp class not define
  27. #include <cool/Regexp.h>            // Include class specification 
  28. #endif
  29.  
  30. // ~CoolRegexp -- Destructor for CoolRegexp class (not inline because it's virtual)
  31. // Input:     None
  32. // Output:    None
  33.  
  34. CoolRegexp::~CoolRegexp () {
  35.   delete [] this->program;
  36. }
  37.  
  38.  
  39. // CoolRegexp -- Copy constructor duplicates its values and state
  40. // Input:    Reference to a Regular Expression 
  41. // Output:   None
  42.  
  43. CoolRegexp::CoolRegexp (const CoolRegexp& rxp) {
  44.   int ind; 
  45.   this->progsize = rxp.progsize;        // Copy regular expression size
  46.   this->program = new char[this->progsize];    // Allocate storage
  47.   for(ind=this->progsize; ind-- != 0;)        // Copy regular expresion
  48.     this->program[ind] = rxp.program[ind];
  49.   this->startp[0] = rxp.startp[0];        // Copy pointers into last
  50.   this->endp[0] = rxp.endp[0];            // Successful "find" operation
  51.   this->regmust = rxp.regmust;            // Copy field
  52.   if (rxp.regmust != NULL) {
  53.     char* dum = rxp.program;
  54.     ind = 0;
  55.     while (dum != rxp.regmust) {
  56.       ++dum;
  57.       ++ind;
  58.     }
  59.     this->regmust = this->program + ind;
  60.   }
  61.   this->regstart = rxp.regstart;        // Copy starting index
  62.   this->reganch = rxp.reganch;            // Copy remaining private data
  63.   this->regmlen = rxp.regmlen;            // Copy remaining private data
  64. }
  65.      
  66.  
  67. // operator== -- Overload the equality operator for the CoolRegexp class. Two CoolRegexp
  68. //               are == if their programs are the same.
  69. // Input:        A reference to a regular expression.
  70. // Output:       Boolean TRUE/FALSE
  71.  
  72. Boolean CoolRegexp::operator== (const CoolRegexp& rxp) const {
  73.   int ind = this->progsize;            // Get regular expression size
  74.   if (ind != rxp.progsize)            // If different size regexp
  75.     return FALSE;                // Return failure
  76.   while(ind-- != 0)                // Else while still characters
  77.     if(this->program[ind] != rxp.program[ind])    // If regexp are different    
  78.       return FALSE;                // Return failure             
  79.   return TRUE;                    // Else same, return success  
  80. }
  81.  
  82.  
  83. // deep_equal -- Two CoolRegexp objects that are deep_equal are both == and have
  84. //               the same startp[0] and endp[0] pointers. This means that they
  85. //               have the same compiled regular expression and they last
  86. //               matched on the same identical string.
  87. // Input:        A reference to a CoolRegexp object.
  88. // Output:       Boolean TRUE/FALSE
  89.  
  90. Boolean CoolRegexp::deep_equal (const CoolRegexp& rxp) const {
  91.   int ind = this->progsize;            // Get regular expression size
  92.   if (ind != rxp.progsize)            // If different size regexp
  93.     return FALSE;                // Return failure
  94.   while(ind-- != 0)                // Else while still characters
  95.     if(this->program[ind] != rxp.program[ind])    // If regexp are different    
  96.       return FALSE;                // Return failure             
  97.   return (this->startp[0] == rxp.startp[0] &&     // Else if same start/end ptrs,
  98.       this->endp[0] == rxp.endp[0]);    // Return TRUE
  99. }   
  100.  
  101. // The remaining code in this file is derived from the  regular expression code
  102. // whose  copyright statement appears  below.  It has been  changed to work
  103. // with the class concepts of C++ and COOL.
  104.  
  105. /*
  106.  * compile and find 
  107.  *
  108.  *    Copyright (c) 1986 by University of Toronto.
  109.  *    Written by Henry Spencer.  Not derived from licensed software.
  110.  *
  111.  *    Permission is granted to anyone to use this software for any
  112.  *    purpose on any computer system, and to redistribute it freely,
  113.  *    subject to the following restrictions:
  114.  *
  115.  *    1. The author is not responsible for the consequences of use of
  116.  *        this software, no matter how awful, even if they arise
  117.  *        from defects in it.
  118.  *
  119.  *    2. The origin of this software must not be misrepresented, either
  120.  *        by explicit claim or by omission.
  121.  *
  122.  *    3. Altered versions must be plainly marked as such, and must not
  123.  *        be misrepresented as being the original software.
  124.  *
  125.  * Beware that some of this code is subtly aware of the way operator
  126.  * precedence is structured in regular expressions.  Serious changes in
  127.  * regular-expression syntax might require a total rethink.
  128.  */
  129.  
  130. /*
  131.  * The "internal use only" fields in regexp.h are present to pass info from
  132.  * compile to execute that permits the execute phase to run lots faster on
  133.  * simple cases.  They are:
  134.  *
  135.  * regstart    char that must begin a match; '\0' if none obvious
  136.  * reganch    is the match anchored (at beginning-of-line only)?
  137.  * regmust    string (pointer into program) that match must include, or NULL
  138.  * regmlen    length of regmust string
  139.  *
  140.  * Regstart and reganch permit very fast decisions on suitable starting points
  141.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  142.  * of lines that cannot possibly match.  The regmust tests are costly enough
  143.  * that compile() supplies a regmust only if the r.e. contains something
  144.  * potentially expensive (at present, the only such thing detected is * or +
  145.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  146.  * supplied because the test in find() needs it and compile() is computing
  147.  * it anyway.
  148.  */
  149.  
  150. /*
  151.  * Structure for regexp "program".  This is essentially a linear encoding
  152.  * of a nondeterministic finite-state machine (aka syntax charts or
  153.  * "railroad normal form" in parsing technology).  Each node is an opcode
  154.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  155.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  156.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  157.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  158.  * opposed to a collection of them) is never concatenated with anything
  159.  * because of operator precedence.)  The operand of some types of node is
  160.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  161.  * particular, the operand of a BRANCH node is the first node of the branch.
  162.  * (NB this is *not* a tree structure:  the tail of the branch connects
  163.  * to the thing following the set of BRANCHes.)  The opcodes are:
  164.  */
  165.  
  166. // definition    number    opnd?    meaning
  167. #define    END    0        // no    End of program.
  168. #define    BOL    1        // no    Match "" at beginning of line.
  169. #define    EOL    2        // no    Match "" at end of line.
  170. #define    ANY    3        // no    Match any one character.
  171. #define    ANYOF    4        // str    Match any character in this string.
  172. #define    ANYBUT    5        // str    Match any character not in this
  173.                 // string.
  174. #define    BRANCH    6        // node    Match this alternative, or the
  175.                 // next...
  176. #define    BACK    7        // no    Match "", "next" ptr points backward.
  177. #define    EXACTLY    8        // str    Match this string.
  178. #define    NOTHING    9        // no    Match empty string.
  179. #define    STAR    10        // node    Match this (simple) thing 0 or more
  180.                 // times.
  181. #define    PLUS    11        // node    Match this (simple) thing 1 or more
  182.                 // times.
  183. #define    OPEN    20        // no    Mark this point in input as start of
  184.                 // #n.
  185. // OPEN+1 is number 1, etc.
  186. #define    CLOSE    30        // no    Analogous to OPEN.
  187.  
  188. /*
  189.  * Opcode notes:
  190.  *
  191.  * BRANCH    The set of branches constituting a single choice are hooked
  192.  *        together with their "next" pointers, since precedence prevents
  193.  *        anything being concatenated to any individual branch.  The
  194.  *        "next" pointer of the last BRANCH in a choice points to the
  195.  *        thing following the whole choice.  This is also where the
  196.  *        final "next" pointer of each individual branch points; each
  197.  *        branch starts with the operand node of a BRANCH node.
  198.  *
  199.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  200.  *        exists to make loop structures possible.
  201.  *
  202.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  203.  *        BRANCH structures using BACK.  Simple cases (one character
  204.  *        per match) are implemented with STAR and PLUS for speed
  205.  *        and to minimize recursive plunges.
  206.  *
  207.  * OPEN,CLOSE    ...are numbered at compile time.
  208.  */
  209.  
  210. /*
  211.  * A node is one char of opcode followed by two chars of "next" pointer.
  212.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  213.  * value is a positive offset from the opcode of the node containing it.
  214.  * An operand, if any, simply follows the node.  (Note that much of the
  215.  * code generation knows about this implicit relationship.)
  216.  *
  217.  * Using two bytes for the "next" pointer is vast overkill for most things,
  218.  * but allows patterns to get big without disasters.
  219.  */
  220.  
  221. #define    OP(p)        (*(p))
  222. #define    NEXT(p)        (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  223. #define    OPERAND(p)    ((p) + 3)
  224.  
  225.  
  226. /*
  227.  * Utility definitions.
  228.  */
  229. #ifndef CHARBITS
  230. #define    UCHARAT(p)    ((int)*(const unsigned char*)(p))
  231. #else
  232. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  233. #endif
  234.  
  235. #define    FAIL(m)    { regerror(m); return(NULL); }
  236. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  237. #define    META    "^$.[()|?+*\\"
  238.  
  239.  
  240. /*
  241.  * Flags to be passed up and down.
  242.  */
  243. #define    HASWIDTH    01    // Known never to match null string.
  244. #define    SIMPLE        02    // Simple enough to be STAR/PLUS operand.
  245. #define    SPSTART        04    // Starts with * or +.
  246. #define    WORST        0    // Worst case.
  247.  
  248.  
  249.  
  250. /////////////////////////////////////////////////////////////////////////
  251. //
  252. //  COMPILE AND ASSOCIATED FUNCTIONS
  253. //
  254. /////////////////////////////////////////////////////////////////////////
  255.  
  256.  
  257. /*
  258.  * Global work variables for compile().
  259.  */
  260. static const char* regparse;    // Input-scan pointer.
  261. static       int   regnpar;    // () count.
  262. static       char  regdummy;
  263. static       char* regcode;    // Code-emit pointer; ®dummy = don't.
  264. static       long  regsize;    // Code size.
  265.  
  266. /*
  267.  * Forward declarations for compile()'s friends.
  268.  */
  269. #ifndef STATIC
  270. #define    STATIC    static
  271. #endif
  272. STATIC       char* reg (int, int*);
  273. STATIC       char* regbranch (int*);
  274. STATIC       char* regpiece (int*);
  275. STATIC       char* regatom (int*);
  276. STATIC       char* regnode (char);
  277. STATIC const char* regnext (register const char*);
  278. STATIC       char* regnext (register char*);
  279. STATIC void        regc (char);
  280. STATIC void        reginsert (char, char*);
  281. STATIC void        regtail (char*, const char*);
  282. STATIC void        regoptail (char*, const char*);
  283.  
  284. #ifdef STRCSPN
  285. STATIC int strcspn ();
  286. #endif
  287.  
  288.  
  289. /*
  290.  - compile - compile a regular expression into internal code
  291.  *
  292.  * We can't allocate space until we know how big the compiled form will be,
  293.  * but we can't compile it (and thus know how big it is) until we've got a
  294.  * place to put the code.  So we cheat:  we compile it twice, once with code
  295.  * generation turned off and size counting turned on, and once "for real".
  296.  * This also means that we don't allocate space until we are sure that the
  297.  * thing really will compile successfully, and we never have to move the
  298.  * code and thus invalidate pointers into it.  (Note that it has to be in
  299.  * one piece because free() must be able to free it all.)
  300.  *
  301.  * Beware that the optimization-preparation code in here knows about some
  302.  * of the structure of the compiled regexp.
  303.  */
  304. void CoolRegexp::compile (const char* exp) {
  305.     register const char* scan;
  306.     register const char* longest;
  307.     register int         len;
  308.              int         flags;
  309.  
  310.     if (exp == NULL) {
  311.       //RAISE (Error, SYM(CoolRegexp), SYM(No_Expr),
  312.       printf ("CoolRegexp::compile(): No expression supplied.\n");
  313.       abort ();
  314.     }
  315.  
  316.     // First pass: determine size, legality.
  317.     regparse = exp;
  318.     regnpar = 1;
  319.     regsize = 0L;
  320.     regcode = ®dummy;
  321.     regc(MAGIC);
  322.     reg(0, &flags);
  323.     this->startp[0] = this->endp[0] = this->searchstring = NULL;
  324.  
  325.     // Small enough for pointer-storage convention? 
  326.     if (regsize >= 32767L) {    // Probably could be 65535L. 
  327.       //RAISE (Error, SYM(CoolRegexp), SYM(Expr_Too_Big),
  328.       printf ("CoolRegexp::compile(): Expression too big.\n");
  329.       abort ();
  330.     }
  331.  
  332.     // Allocate space. 
  333.     if (this->program != NULL) delete [] this->program;  
  334.     this->program = new char[regsize];
  335.     this->progsize = (int) regsize;
  336.  
  337.     if (this->program == NULL) {
  338.       //RAISE (Error, SYM(CoolRegexp), SYM(Out_Of_Memory),
  339.       printf ("CoolRegexp::compile(): Out of memory.\n"); 
  340.       abort ();
  341.     }
  342.  
  343.     // Second pass: emit code.
  344.     regparse = exp;
  345.     regnpar = 1;
  346.     regcode = this->program;
  347.     regc(MAGIC);
  348.     reg(0, &flags);
  349.  
  350.     // Dig out information for optimizations.
  351.     this->regstart = '\0';        // Worst-case defaults.
  352.     this->reganch = 0;
  353.     this->regmust = NULL;
  354.     this->regmlen = 0;
  355.     scan = this->program + 1;    // First BRANCH.
  356.     if (OP(regnext(scan)) == END) {    // Only one top-level choice.
  357.     scan = OPERAND(scan);
  358.  
  359.     // Starting-point info.
  360.     if (OP(scan) == EXACTLY)
  361.         this->regstart = *OPERAND(scan);
  362.     else if (OP(scan) == BOL)
  363.         this->reganch++;
  364.  
  365.      //
  366.      // If there's something expensive in the r.e., find the longest
  367.      // literal string that must appear and make it the regmust.  Resolve
  368.      // ties in favor of later strings, since the regstart check works
  369.      // with the beginning of the r.e. and avoiding duplication
  370.      // strengthens checking.  Not a strong reason, but sufficient in the
  371.      // absence of others. 
  372.      //
  373.     if (flags & SPSTART) {
  374.         longest = NULL;
  375.         len = 0;
  376.         for (; scan != NULL; scan = regnext(scan))
  377.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  378.             longest = OPERAND(scan);
  379.             len = strlen(OPERAND(scan));
  380.         }
  381.         this->regmust = longest;
  382.         this->regmlen = len;
  383.     }
  384.     }
  385. }
  386.  
  387.  
  388. /*
  389.  - reg - regular expression, i.e. main body or parenthesized thing
  390.  *
  391.  * Caller must absorb opening parenthesis.
  392.  *
  393.  * Combining parenthesis handling with the base level of regular expression
  394.  * is a trifle forced, but the need to tie the tails of the branches to what
  395.  * follows makes it hard to avoid.
  396.  */
  397. static char* reg (int paren, int *flagp) {
  398.     register char* ret;
  399.     register char* br;
  400.     register char* ender;
  401.     register int   parno;
  402.              int   flags;
  403.  
  404.     *flagp = HASWIDTH;        // Tentatively.
  405.  
  406.     // Make an OPEN node, if parenthesized.
  407.     if (paren) {
  408.     if (regnpar >= NSUBEXP) {
  409.       //RAISE (Error, SYM(CoolRegexp), SYM(Too_Many_Parens),
  410.       printf ("CoolRegexp::compile(): Too many parentheses.\n");
  411.       abort ();
  412.         }
  413.     parno = regnpar;
  414.     regnpar++;
  415.     ret = regnode(OPEN + parno);
  416.     }
  417.     else
  418.     ret = NULL;
  419.  
  420.     // Pick up the branches, linking them together.
  421.     br = regbranch(&flags);
  422.     if (br == NULL)
  423.     return (NULL);
  424.     if (ret != NULL)
  425.     regtail(ret, br);    // OPEN -> first.
  426.     else
  427.     ret = br;
  428.     if (!(flags & HASWIDTH))
  429.     *flagp &= ~HASWIDTH;
  430.     *flagp |= flags & SPSTART;
  431.     while (*regparse == '|') {
  432.     regparse++;
  433.     br = regbranch(&flags);
  434.     if (br == NULL)
  435.         return (NULL);
  436.     regtail(ret, br);    // BRANCH -> BRANCH.
  437.     if (!(flags & HASWIDTH))
  438.         *flagp &= ~HASWIDTH;
  439.     *flagp |= flags & SPSTART;
  440.       }
  441.  
  442.     // Make a closing node, and hook it on the end.
  443.     ender = regnode((paren) ? CLOSE + parno : END);
  444.     regtail(ret, ender);
  445.  
  446.     // Hook the tails of the branches to the closing node.
  447.     for (br = ret; br != NULL; br = regnext(br))
  448.     regoptail(br, ender);
  449.  
  450.     // Check for proper termination.
  451.     if (paren && *regparse++ != ')') {
  452.         //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Parens),
  453.         printf ("CoolRegexp::compile(): Unmatched parentheses.\n");
  454.     abort ();
  455.     }
  456.     else if (!paren && *regparse != '\0') {
  457.         if (*regparse == ')') {
  458.             //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Parens),
  459.             printf ("CoolRegexp::compile(): Unmatched parentheses.\n");
  460.         abort ();
  461.     }
  462.     else {
  463.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  464.         printf ("CoolRegexp::compile(): Internal error.\n");
  465.         abort ();
  466.         }
  467.     // NOTREACHED
  468.     }
  469.     return (ret);
  470. }
  471.  
  472.  
  473. /*
  474.  - regbranch - one alternative of an | operator
  475.  *
  476.  * Implements the concatenation operator.
  477.  */
  478. static char* regbranch (int *flagp) {
  479.     register char* ret;
  480.     register char* chain;
  481.     register char* latest;
  482.     int                  flags;
  483.  
  484.     *flagp = WORST;        // Tentatively.
  485.  
  486.     ret = regnode(BRANCH);
  487.     chain = NULL;
  488.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  489.     latest = regpiece(&flags);
  490.     if (latest == NULL)
  491.         return (NULL);
  492.     *flagp |= flags & HASWIDTH;
  493.     if (chain == NULL)    // First piece.
  494.         *flagp |= flags & SPSTART;
  495.     else
  496.         regtail(chain, latest);
  497.     chain = latest;
  498.     }
  499.     if (chain == NULL)        // Loop ran zero times.
  500.     regnode(NOTHING);
  501.  
  502.     return (ret);
  503. }
  504.  
  505.  
  506. /*
  507.  - regpiece - something followed by possible [*+?]
  508.  *
  509.  * Note that the branching code sequences used for ? and the general cases
  510.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  511.  * both the endmarker for their branch list and the body of the last branch.
  512.  * It might seem that this node could be dispensed with entirely, but the
  513.  * endmarker role is not redundant.
  514.  */
  515. static char* regpiece (int *flagp) {
  516.     register char* ret;
  517.     register char  op;
  518.     register char* next;
  519.     int            flags;
  520.  
  521.     ret = regatom(&flags);
  522.     if (ret == NULL)
  523.     return (NULL);
  524.  
  525.     op = *regparse;
  526.     if (!ISMULT(op)) {
  527.     *flagp = flags;
  528.     return (ret);
  529.     }
  530.  
  531.     if (!(flags & HASWIDTH) && op != '?') {
  532.         //RAISE (Error, SYM(CoolRegexp), SYM(Empty_Operand),
  533.         printf ("CoolRegexp::compile() : *+ operand could be empty.\n");
  534.     abort ();
  535.     }
  536.     *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
  537.  
  538.     if (op == '*' && (flags & SIMPLE))
  539.     reginsert(STAR, ret);
  540.     else if (op == '*') {
  541.     // Emit x* as (x&|), where & means "self".
  542.     reginsert(BRANCH, ret);    // Either x
  543.     regoptail(ret, regnode(BACK));    // and loop
  544.     regoptail(ret, ret);    // back
  545.     regtail(ret, regnode(BRANCH));    // or
  546.     regtail(ret, regnode(NOTHING));    // null.
  547.     }
  548.     else if (op == '+' && (flags & SIMPLE))
  549.     reginsert(PLUS, ret);
  550.     else if (op == '+') {
  551.     // Emit x+ as x(&|), where & means "self".
  552.     next = regnode(BRANCH);    // Either
  553.     regtail(ret, next);
  554.     regtail(regnode(BACK), ret);    // loop back
  555.     regtail(next, regnode(BRANCH));    // or
  556.     regtail(ret, regnode(NOTHING));    // null.
  557.     }
  558.     else if (op == '?') {
  559.     // Emit x? as (x|)
  560.     reginsert(BRANCH, ret);    // Either x
  561.     regtail(ret, regnode(BRANCH));    // or
  562.     next = regnode(NOTHING);// null.
  563.     regtail(ret, next);
  564.     regoptail(ret, next);
  565.     }
  566.     regparse++;
  567.     if (ISMULT(*regparse)) {
  568.         //RAISE (Error, SYM(CoolRegexp), SYM(Nested_Operand),
  569.         printf ("CoolRegexp::compile(): Nested *?+.\n");
  570.     abort ();
  571.     }
  572.     return (ret);
  573. }
  574.  
  575.  
  576. /*
  577.  - regatom - the lowest level
  578.  *
  579.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  580.  * it can turn them into a single node, which is smaller to store and
  581.  * faster to run.  Backslashed characters are exceptions, each becoming a
  582.  * separate node; the code is simpler that way and it's not worth fixing.
  583.  */
  584. static char* regatom (int *flagp) {
  585.     register char* ret;
  586.              int   flags;
  587.  
  588.     *flagp = WORST;        // Tentatively.
  589.  
  590.     switch (*regparse++) {
  591.     case '^':
  592.         ret = regnode(BOL);
  593.         break;
  594.     case '$':
  595.         ret = regnode(EOL);
  596.         break;
  597.     case '.':
  598.         ret = regnode(ANY);
  599.         *flagp |= HASWIDTH | SIMPLE;
  600.         break;
  601.     case '[':{
  602.         register int    rxpclass;
  603.         register int    rxpclassend;
  604.  
  605.         if (*regparse == '^') {    // Complement of range.
  606.             ret = regnode(ANYBUT);
  607.             regparse++;
  608.         }
  609.         else
  610.             ret = regnode(ANYOF);
  611.         if (*regparse == ']' || *regparse == '-')
  612.             regc(*regparse++);
  613.         while (*regparse != '\0' && *regparse != ']') {
  614.             if (*regparse == '-') {
  615.             regparse++;
  616.             if (*regparse == ']' || *regparse == '\0')
  617.                 regc('-');
  618.             else {
  619.                 rxpclass = UCHARAT(regparse - 2) + 1;
  620.                 rxpclassend = UCHARAT(regparse);
  621.                 if (rxpclass > rxpclassend + 1) {
  622.                    //RAISE (Error, SYM(CoolRegexp), SYM(Invalid_Range),
  623.                    printf ("CoolRegexp::compile(): Invalid range in [].\n");
  624.                    abort ();
  625.                             }
  626.                 for (; rxpclass <= rxpclassend; rxpclass++)
  627.                 regc(rxpclass);
  628.                 regparse++;
  629.             }
  630.             }
  631.             else
  632.             regc(*regparse++);
  633.         }
  634.         regc('\0');
  635.         if (*regparse != ']') {
  636.                     //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Bracket),
  637.                     printf ("CoolRegexp::compile(): Unmatched [].\n");
  638.             abort ();
  639.             }
  640.         regparse++;
  641.         *flagp |= HASWIDTH | SIMPLE;
  642.         }
  643.         break;
  644.     case '(':
  645.         ret = reg(1, &flags);
  646.         if (ret == NULL)
  647.         return (NULL);
  648.         *flagp |= flags & (HASWIDTH | SPSTART);
  649.         break;
  650.     case '\0':
  651.     case '|':
  652.     case ')':
  653.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  654.             printf ("CoolRegexp::compile(): Internal error.\n"); // Never here
  655.         abort ();
  656.     case '?':
  657.     case '+':
  658.     case '*':
  659.         //RAISE (Error, SYM(CoolRegexp), SYM(No_Operand),
  660.             printf ("CoolRegexp::compile(): ?+* follows nothing.\n");
  661.         abort ();
  662.     case '\\':
  663.         if (*regparse == '\0') {
  664.             //RAISE (Error, SYM(CoolRegexp), SYM(Trailing_Backslash),
  665.                 printf ("CoolRegexp::compile(): Trailing backslash.\n");
  666.         abort ();
  667.             }
  668.         ret = regnode(EXACTLY);
  669.         regc(*regparse++);
  670.         regc('\0');
  671.         *flagp |= HASWIDTH | SIMPLE;
  672.         break;
  673.     default:{
  674.         register int    len;
  675.         register char   ender;
  676.  
  677.         regparse--;
  678.         len = strcspn(regparse, META);
  679.         if (len <= 0) {
  680.             //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  681.                     printf ("CoolRegexp::compile(): Internal error.\n");
  682.             abort ();
  683.                 }
  684.         ender = *(regparse + len);
  685.         if (len > 1 && ISMULT(ender))
  686.             len--;    // Back off clear of ?+* operand.
  687.         *flagp |= HASWIDTH;
  688.         if (len == 1)
  689.             *flagp |= SIMPLE;
  690.         ret = regnode(EXACTLY);
  691.         while (len > 0) {
  692.             regc(*regparse++);
  693.             len--;
  694.         }
  695.         regc('\0');
  696.         }
  697.         break;
  698.     }
  699.     return (ret);
  700. }
  701.  
  702.  
  703. /*
  704.  - regnode - emit a node
  705.    Location.
  706.  */
  707. static char* regnode (char op) {
  708.     register char* ret;
  709.     register char* ptr;
  710.  
  711.     ret = regcode;
  712.     if (ret == ®dummy) {
  713.     regsize += 3;
  714.     return (ret);
  715.     }
  716.  
  717.     ptr = ret;
  718.     *ptr++ = op;
  719.     *ptr++ = '\0';        // Null "next" pointer.
  720.     *ptr++ = '\0';
  721.     regcode = ptr;
  722.  
  723.     return (ret);
  724. }
  725.  
  726.  
  727. /*
  728.  - regc - emit (if appropriate) a byte of code
  729.  */
  730. static void regc (char b) {
  731.     if (regcode != ®dummy)
  732.     *regcode++ = b;
  733.     else
  734.     regsize++;
  735. }
  736.  
  737.  
  738. /*
  739.  - reginsert - insert an operator in front of already-emitted operand
  740.  *
  741.  * Means relocating the operand.
  742.  */
  743. static void reginsert (char op, char* opnd) {
  744.     register char* src;
  745.     register char* dst;
  746.     register char* place;
  747.  
  748.     if (regcode == ®dummy) {
  749.     regsize += 3;
  750.     return;
  751.     }
  752.  
  753.     src = regcode;
  754.     regcode += 3;
  755.     dst = regcode;
  756.     while (src > opnd)
  757.     *--dst = *--src;
  758.  
  759.     place = opnd;        // Op node, where operand used to be.
  760.     *place++ = op;
  761.     *place++ = '\0';
  762.     *place++ = '\0';
  763. }
  764.  
  765.  
  766. /*
  767.  - regtail - set the next-pointer at the end of a node chain
  768.  */
  769. static void regtail (char* p, const char* val) {
  770.     register char* scan;
  771.     register char* temp;
  772.     register int   offset;
  773.  
  774.     if (p == ®dummy)
  775.     return;
  776.  
  777.     // Find last node.
  778.     scan = p;
  779.     for (;;) {
  780.     temp = regnext(scan);
  781.     if (temp == NULL)
  782.         break;
  783.     scan = temp;
  784.     }
  785.  
  786.     if (OP(scan) == BACK)
  787.     offset = (const char*)scan - val;
  788.     else
  789.     offset = val - scan;
  790.     *(scan + 1) = (offset >> 8) & 0377;
  791.     *(scan + 2) = offset & 0377;
  792. }
  793.  
  794.  
  795. /*
  796.  - regoptail - regtail on operand of first argument; nop if operandless
  797.  */
  798. static void regoptail (char* p, const char* val) {
  799.     // "Operandless" and "op != BRANCH" are synonymous in practice.
  800.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  801.     return;
  802.     regtail(OPERAND(p), val);
  803. }
  804.  
  805.  
  806.  
  807. ////////////////////////////////////////////////////////////////////////
  808. // 
  809. //  find and friends
  810. // 
  811. ////////////////////////////////////////////////////////////////////////
  812.  
  813.  
  814. /*
  815.  * Global work variables for find().
  816.  */
  817. static const char*  reginput;    // String-input pointer.
  818. static const char*  regbol;    // Beginning of input, for ^ check.
  819. static const char* *regstartp;    // Pointer to startp array.
  820. static const char* *regendp;    // Ditto for endp.
  821.  
  822. /*
  823.  * Forwards.
  824.  */
  825. STATIC int regtry (const char*, const char*[NSUBEXP],
  826.            const char*[NSUBEXP], const char*);
  827. STATIC int regmatch (const char*);
  828. STATIC int regrepeat (const char*);
  829.  
  830. #ifdef DEBUG
  831. int          regnarrate = 0;
  832. void         regdump ();
  833. STATIC char* regprop ();
  834. #endif
  835.  
  836.  
  837. /*
  838.  - find - match a regexpr against a string
  839.  */
  840. Boolean CoolRegexp::find (const char* string) {
  841.     register const char* s;
  842.     
  843.     this->searchstring = string;
  844.  
  845.      // Check validity of program.
  846.     if (UCHARAT(this->program) != MAGIC) {
  847.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  848.         printf ("CoolRegexp::find(): Compiled regular expression corrupted.\n");
  849.     abort ();
  850.     }
  851.     
  852.     // If there is a "must appear" string, look for it.
  853.     if (this->regmust != NULL) {
  854.     s = string;
  855.     while ((s = strchr(s, this->regmust[0])) != NULL) {
  856.         if (strncmp(s, this->regmust, this->regmlen) == 0)
  857.         break;        // Found it.
  858.         s++;
  859.     }
  860.     if (s == NULL)        // Not present.
  861.         return (0);
  862.     }
  863.      
  864.     // Mark beginning of line for ^ .
  865.     regbol = string;
  866.  
  867.     // Simplest case:  anchored match need be tried only once.
  868.     if (this->reganch)
  869.     return (regtry(string, this->startp, this->endp, this->program));
  870.     
  871.     // Messy cases:  unanchored match.
  872.     s = string;
  873.     if (this->regstart != '\0')
  874.     // We know what char it must start with.
  875.     while ((s = strchr(s, this->regstart)) != NULL) {
  876.         if (regtry(s, this->startp, this->endp, this->program))
  877.         return (1);
  878.         s++;
  879.       
  880.     }
  881.     else
  882.     // We don't -- general case.
  883.     do {
  884.         if (regtry(s, this->startp, this->endp, this->program))
  885.         return (1);
  886.     } while (*s++ != '\0');
  887.     
  888.     // Failure.
  889.     return (0);
  890. }
  891.  
  892.  
  893. /*
  894.  - regtry - try match at specific point
  895.    0 failure, 1 success
  896.  */
  897. static int regtry (const char* string, const char* *start,
  898.            const char* *end, const char* prog) {
  899.     register       int    i;
  900.     register const char* *sp1;
  901.     register const char* *ep;
  902.  
  903.     reginput = string;
  904.     regstartp = start;
  905.     regendp = end;
  906.  
  907.     sp1 = start;
  908.     ep = end;
  909.     for (i = NSUBEXP; i > 0; i--) {
  910.     *sp1++ = NULL;
  911.     *ep++ = NULL;
  912.     }
  913.     if (regmatch(prog + 1)) {
  914.     start[0] = string;
  915.     end[0] = reginput;
  916.     return (1);
  917.     }
  918.     else
  919.     return (0);
  920. }
  921.  
  922.  
  923. /*
  924.  - regmatch - main matching routine
  925.  *
  926.  * Conceptually the strategy is simple:  check to see whether the current
  927.  * node matches, call self recursively to see whether the rest matches,
  928.  * and then act accordingly.  In practice we make some effort to avoid
  929.  * recursion, in particular by going through "ordinary" nodes (that don't
  930.  * need to know whether the rest of the match failed) by a loop instead of
  931.  * by recursion.
  932.  * 0 failure, 1 success
  933.  */
  934. static int regmatch (const char* prog) {
  935.     register const char* scan;    // Current node.
  936.              const char* next;    // Next node.
  937.  
  938.     scan = prog;
  939.  
  940.     while (scan != NULL) {
  941.  
  942.     next = regnext(scan);
  943.  
  944.     switch (OP(scan)) {
  945.         case BOL:
  946.         if (reginput != regbol)
  947.             return (0);
  948.         break;
  949.         case EOL:
  950.         if (*reginput != '\0')
  951.             return (0);
  952.         break;
  953.         case ANY:
  954.         if (*reginput == '\0')
  955.             return (0);
  956.         reginput++;
  957.         break;
  958.         case EXACTLY:{
  959.             register int         len;
  960.             register const char* opnd;
  961.  
  962.             opnd = OPERAND(scan);
  963.             // Inline the first character, for speed.
  964.             if (*opnd != *reginput)
  965.             return (0);
  966.             len = strlen(opnd);
  967.             if (len > 1 && strncmp(opnd, reginput, len) != 0)
  968.             return (0);
  969.             reginput += len;
  970.         }
  971.         break;
  972.         case ANYOF:
  973.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  974.             return (0);
  975.         reginput++;
  976.         break;
  977.         case ANYBUT:
  978.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  979.             return (0);
  980.         reginput++;
  981.         break;
  982.         case NOTHING:
  983.         break;
  984.         case BACK:
  985.         break;
  986.         case OPEN + 1:
  987.         case OPEN + 2:
  988.         case OPEN + 3:
  989.         case OPEN + 4:
  990.         case OPEN + 5:
  991.         case OPEN + 6:
  992.         case OPEN + 7:
  993.         case OPEN + 8:
  994.         case OPEN + 9:{
  995.             register       int    no;
  996.             register const char* save;
  997.  
  998.             no = OP(scan) - OPEN;
  999.             save = reginput;
  1000.  
  1001.             if (regmatch(next)) {
  1002.  
  1003.             //
  1004.             // Don't set startp if some later invocation of the
  1005.             // same parentheses already has. 
  1006.             //
  1007.             if (regstartp[no] == NULL)
  1008.                 regstartp[no] = save;
  1009.             return (1);
  1010.             }
  1011.             else
  1012.             return (0);
  1013.         }
  1014.         break;
  1015.         case CLOSE + 1:
  1016.         case CLOSE + 2:
  1017.         case CLOSE + 3:
  1018.         case CLOSE + 4:
  1019.         case CLOSE + 5:
  1020.         case CLOSE + 6:
  1021.         case CLOSE + 7:
  1022.         case CLOSE + 8:
  1023.         case CLOSE + 9:{
  1024.             register       int    no;
  1025.             register const char* save;
  1026.  
  1027.             no = OP(scan) - CLOSE;
  1028.             save = reginput;
  1029.  
  1030.             if (regmatch(next)) {
  1031.  
  1032.             //
  1033.             // Don't set endp if some later invocation of the
  1034.             // same parentheses already has. 
  1035.             //
  1036.             if (regendp[no] == NULL)
  1037.                 regendp[no] = save;
  1038.             return (1);
  1039.             }
  1040.             else
  1041.             return (0);
  1042.         }
  1043.         break;
  1044.         case BRANCH:{
  1045.           
  1046.           register const char* save;
  1047.  
  1048.             if (OP(next) != BRANCH)    // No choice.
  1049.             next = OPERAND(scan);    // Avoid recursion.
  1050.             else {
  1051.             do {
  1052.                 save = reginput;
  1053.                 if (regmatch(OPERAND(scan)))
  1054.                 return (1);
  1055.                 reginput = save;
  1056.                 scan = regnext(scan);
  1057.             } while (scan != NULL && OP(scan) == BRANCH);
  1058.             return (0);
  1059.             // NOTREACHED
  1060.             }
  1061.         }
  1062.         break;
  1063.         case STAR:
  1064.         case PLUS:{
  1065.           register char   nextch;
  1066.             register int        no;
  1067.             register const char* save;
  1068.             register int        min_no;
  1069.  
  1070.             //
  1071.             // Lookahead to avoid useless match attempts when we know
  1072.             // what character comes next. 
  1073.             //
  1074.             nextch = '\0';
  1075.             if (OP(next) == EXACTLY)
  1076.             nextch = *OPERAND(next);
  1077.             min_no = (OP(scan) == STAR) ? 0 : 1;
  1078.             save = reginput;
  1079.             no = regrepeat(OPERAND(scan));
  1080.             while (no >= min_no) {
  1081.             // If it could work, try it.
  1082.             if (nextch == '\0' || *reginput == nextch)
  1083.                 if (regmatch(next))
  1084.                 return (1);
  1085.             // Couldn't or didn't -- back up.
  1086.             no--;
  1087.             reginput = save + no;
  1088.             }
  1089.             return (0);
  1090.         }
  1091.         break;
  1092.         case END:
  1093.          return (1);    // Success!
  1094.  
  1095.         default:
  1096.             //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1097.                 printf ("CoolRegexp::find(): Internal error -- memory corrupted.\n");
  1098.         abort ();
  1099.     }
  1100.     scan = next;
  1101.     }
  1102.  
  1103.     // 
  1104.     //  We get here only if there's trouble -- normally "case END" is the
  1105.     //  terminating point. 
  1106.     // 
  1107.     //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1108.     printf ("CoolRegexp::find(): Internal error -- corrupted pointers.\n");
  1109.     abort ();
  1110.     return (0);
  1111. }
  1112.  
  1113.  
  1114. /*
  1115.  - regrepeat - repeatedly match something simple, report how many
  1116.  */
  1117. static int regrepeat (const char* p) {
  1118.     register       int   count = 0;
  1119.     register const char* scan;
  1120.     register const char* opnd;
  1121.  
  1122.     scan = reginput;
  1123.     opnd = OPERAND(p);
  1124.     switch (OP(p)) {
  1125.     case ANY:
  1126.         count = strlen(scan);
  1127.         scan += count;
  1128.         break;
  1129.     case EXACTLY:
  1130.         while (*opnd == *scan) {
  1131.         count++;
  1132.         scan++;
  1133.         }
  1134.         break;
  1135.     case ANYOF:
  1136.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1137.         count++;
  1138.         scan++;
  1139.         }
  1140.         break;
  1141.     case ANYBUT:
  1142.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1143.         count++;
  1144.         scan++;
  1145.         }
  1146.         break;
  1147.     default:        // Oh dear.  Called inappropriately.
  1148.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1149.         printf ("CoolRegexp::find(): Internal error.\n");
  1150.         abort ();
  1151.     }
  1152.     reginput = scan;
  1153.     return (count);
  1154. }
  1155.  
  1156.  
  1157. /*
  1158.  - regnext - dig the "next" pointer out of a node
  1159.  */
  1160. static const char* regnext (register const char* p) {
  1161.     register int offset;
  1162.  
  1163.     if (p == ®dummy)
  1164.     return (NULL);
  1165.  
  1166.     offset = NEXT(p);
  1167.     if (offset == 0)
  1168.     return (NULL);
  1169.  
  1170.     if (OP(p) == BACK)
  1171.     return (p - offset);
  1172.     else
  1173.     return (p + offset);
  1174. }
  1175.  
  1176.  
  1177. static char* regnext (register char* p) {
  1178.     register int offset;
  1179.  
  1180.     if (p == ®dummy)
  1181.     return (NULL);
  1182.  
  1183.     offset = NEXT(p);
  1184.     if (offset == 0)
  1185.     return (NULL);
  1186.  
  1187.     if (OP(p) == BACK)
  1188.     return (p - offset);
  1189.     else
  1190.     return (p + offset);
  1191. }
  1192.